Modern computer systems often comprise a plurality of operating devices such as processors and I/O controllers and a shared resource such as a shared memory. The shared memory is made available to each of the plurality of devices in the computer system as a memory service for the storage of data. Typically, the processors, I/O controllers and the shared resource are coupled to one another by a bus and only one device at a time can access the shared resource over the bus. Accordingly, it is necessary to provide an arbitration scheme in the computer system to decide which one of several devices that may be requesting access to the shared memory will be granted control of the bus for the performance of read and write operations with the shared memory.
A known method for implementing an arbitration scheme in a computer system consists of reducing a flow chart description of the logic required for the arbitration scheme into a gate level logic circuit implementation through the use of karnaugh maps. Typically, the gate level implementation comprises a state machine wherein input signals corresponding to requests by the devices for access to the shared resource result in the generation of state variables that indicate which device has won the arbitration. A problem with the presently utilized gate level implementations for arbitration schemes is that the design uses only state variables and input signals to generate the next state variables. In addition, unused or invalid states for the state variables of the state machine are typically placed in the logic design so as to transition to a null state or to zero. Thus, presently known arbitration scheme implementations often require the use of a large number of components and gates to generate the necessary state variables, resulting in excessive cost and complexity.